package com.nanbei.dp;

import com.alibaba.fastjson.JSONObject;

/**
 * @ClassDescription: （斐波拉西数列）动态规划
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/4 16:49
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(13));
        System.out.println(fibonacciT(13));



    }

    // 使用一维数组进行求解
    public static int fibonacci(int n) {
        int[] ints = new int[n + 1];
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        ints[0] = 0;
        ints[1] = 1;
        for (int i = 2; i <= n; i++) {
            ints[i] = ints[i - 1] + ints[i - 2];
        }
        return ints[n];
    }

    // 经过一维数组降维后 使用变量进行代替
    public static int fibonacciT(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        int c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}
